/*
 * @Author: TC
 * @Date: 2023-02-17 11:00:25
 * @LastEditTime: 2023-02-17 16:12:01
 * @Description: 
 */

/**
 * 排序
 */
export namespace nsSort {

    /**
     * 冒泡排序
     * @param arr 数组
     * @returns 
     */
    export function bubbleSort(arr: number[]) {
        var len = arr.length;
        for (var i = 0; i < len - 1; i++) {
            for (var j = 0; j < len - 1 - i; j++) {
                // 相邻元素两两对比
                if (arr[j] > arr[j + 1]) {
                    // 元素交换
                    var temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }

    /**
     * 选择排序
     * @param arr 数组
     * @returns 
     */
    export function selectionSort(arr: number[]) {
        var len = arr.length;
        var minIndex = 0, temp = 0;
        for (var i = 0; i < len - 1; i++) {
            minIndex = i;
            for (var j = i + 1; j < len; j++) {
                //寻找最小的数 
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            //将最小数的索引保存
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        return arr;
    }

    /**
     * 插入排序
     * @param arr 数组
     * @returns 
     */
    export function insertionSort(arr: number[]) {
        var len = arr.length;
        var preIndex = 0, current = 0;
        for (var i = 1; i < len; i++) {
            preIndex = i - 1;
            current = arr[i];
            while (preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex + 1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex + 1] = current;
        }
        return arr;
    }

    /**
     * 希尔排序
     * @param arr 数组
     * @returns 
     */
    export function shellSort(arr: number[]) {
        var len = arr.length, temp = 0, gap = 1;
        //动态定义间隔序列
        while (gap < len / 3) {
            gap = gap * 3 + 1;
        }
        for (gap; gap > 0; gap = Math.floor(gap / 3)) {
            for (var i = gap; i < len; i++) {
                temp = arr[i];
                for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
                    arr[j + gap] = arr[j];
                }
                arr[j + gap] = temp;
            }
        }
        return arr;
    }

    /**
     * 归并排序
     * @param arr 数组
     * @returns 
     */
    export function mergeSort(arr: number[]) {
        function merge(left: number[], right: number[]) {
            var result = [];
            while (left.length && right.length) {
                if (left[0] <= right[0]) {
                    result.push(left.shift());
                } else {
                    result.push(right.shift());
                }
            }

            while (left.length)
                result.push(left.shift());

            while (right.length)
                result.push(right.shift());

            return result;
        }
        var len = arr.length;
        if (len < 2) {
            return arr;
        }
        var middle = Math.floor(len / 2),
            left = arr.slice(0, middle),
            right = arr.slice(middle);
        return merge(this.mergeSort(left), this.mergeSort(right));
    }

    /**
     * 快速排序
     * @param arr 数组
     * @param left 左
     * @param right 右
     * @returns 
     */
    export function quickSort(arr: number[], left: number, right: number) {
        // 分区操作
        function partition(arr: number[], left: number, right: number) {
            var pivot = left,
                index = pivot + 1;
            // 设定基准值（pivot）
            for (var i = index; i <= right; i++) {
                if (arr[i] < arr[pivot]) {
                    swap(arr, i, index);
                    index++;
                }
            }
            swap(arr, pivot, index - 1);
            return index - 1;
        }
        function swap(arr: number[], i: number, j: number) {
            var temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        var len = arr.length,
            partitionIndex = 0,
            left = typeof left != 'number' ? 0 : left,
            right = typeof right != 'number' ? len - 1 : right;

        if (left < right) {
            partitionIndex = partition(arr, left, right);
            this.quickSort(arr, left, partitionIndex - 1);
            this.quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }

    /**
     * 堆排序
     * @param arr 数组
     * @returns 
     */
    export function buildMaxHeap(arr: number[]) {
        var len = 0;
        //建立大顶堆
        function buildMaxHeap(arr: number[]) {
            len = arr.length;
            for (var i = Math.floor(len / 2); i >= 0; i--) {
                heapify(arr, i);
            }
        }
        //堆调整
        function heapify(arr: number[], i: number) {
            var left = 2 * i + 1,
                right = 2 * i + 2,
                largest = i;

            if (left < len && arr[left] > arr[largest]) {
                largest = left;
            }

            if (right < len && arr[right] > arr[largest]) {
                largest = right;
            }

            if (largest != i) {
                swap(arr, i, largest);
                heapify(arr, largest);
            }
        }

        function swap(arr: number[], i: number, j: number) {
            var temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        buildMaxHeap(arr);
        for (var i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            len--;
            heapify(arr, 0);
        }
        return arr;
    }

    /**
     * 计数排序
     * @param arr 数组
     * @param maxValue 最大值
     * @returns 
     */
    export function countingSort(arr: number[], maxValue: number) {
        var bucket = new Array(maxValue + 1),
            sortedIndex = 0;
        var arrLen = arr.length,
            bucketLen = maxValue + 1;
        for (var i = 0; i < arrLen; i++) {
            if (!bucket[arr[i]]) {
                bucket[arr[i]] = 0;
            }
            bucket[arr[i]]++;
        }
        for (var j = 0; j < bucketLen; j++) {
            while (bucket[j] > 0) {
                arr[sortedIndex++] = j;
                bucket[j]--;
            }
        }
        return arr;
    }

    /**
     * 桶排序
     * @param arr 数组
     * @returns 
     */
    export function bucketSort(arr: number[]) {
        if (arr.length === 0) {
            return arr;
        }
        var i = 0;
        var minValue = arr[0];
        var maxValue = arr[0];
        for (i = 1; i < arr.length; i++) {
            if (arr[i] < minValue) {
                minValue = arr[i];                // 输入数据的最小值
            } else if (arr[i] > maxValue) {
                maxValue = arr[i];                // 输入数据的最大值
            }
        }
        //桶的初始化
        var DEFAULT_BUCKET_SIZE = 5;            // 设置桶的默认数量为5
        var bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
        var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
        var buckets = new Array(bucketCount);
        for (i = 0; i < buckets.length; i++) {
            buckets[i] = [];
        }
        //利用映射函数将数据分配到各个桶中
        for (i = 0; i < arr.length; i++) {
            buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
        }
        arr.length = 0;
        for (i = 0; i < buckets.length; i++) {
            //对每个桶进行排序，这里使用了插入排序
            this.insertionSort(buckets[i]);
            for (var j = 0; j < buckets[i].length; j++) {
                arr.push(buckets[i][j]);
            }
        }
        return arr;
    }

    /**
     * 基数排序
     * @param arr 数组
     * @param maxDigit 最大数
     * @returns 
     */
    export function radixSort(arr: number[], maxDigit: number) {
        var counter = [];
        var mod = 10;
        var dev = 1;
        for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            for (var j = 0; j < arr.length; j++) {
                var bucket = Number((arr[j] % mod) / dev);
                if (counter[bucket] == null) {
                    counter[bucket] = [];
                }
                counter[bucket].push(arr[j]);
            }
            var pos = 0;
            for (var j = 0; j < counter.length; j++) {
                var value = null;
                if (counter[j] != null) {
                    while ((value = counter[j].shift()) != null) {
                        arr[pos++] = value;
                    }
                }
            }
        }
        return arr;
    }
}
